#include <cstdlib>
#include <cstring>
#include <iostream>
#include <math.h>
using namespace std;
#define M 2048
int x[M]={0};  // 最优解
int dp[M][M]; // 最优值

// 转化为0-1背包问题
//           效益度     约束     最优值   最优解
//0-1背包    价值v      重量w      m        x
//购物     渴望程度v    价格p      dp       X


// 自底向上计算最优值
void Knapsack(int *v, int *p, int N, int n, int dp[][M])
{   //v是渴望程度，p是价格，N是预算，n是商品个数
    //dp[i][j]是在 预算为j，能买的物品为i~n时，所能达到的最大渴望程度和
    int jMax, j, i;

    // 计算仅第n个物品可买时，dp[n][j]的值。
    jMax = (p[n] - 1) < N ? (p[n] - 1) : N;
    for (j = 0; j <= jMax; j++)//预算0 ~ p[n]-1时，dp为0
        dp[n][j] = 0;
    for (j = p[n]; j <= N; j++)//预算p[n] ~ N时，dp为v[n]
        dp[n][j] = v[n];
    

    for (i = n - 1; i > 1; i--)//自底向上开始求解最优值
    {
        jMax = (p[i] - 1) < N ? (p[i] - 1) : N;
        for (j = 0; j <= jMax; j++)//预算0 ~ p[i]-1时
            dp[i][j] = dp[i + 1][j];
        for (j = p[i]; j <= N; j++)//预算p[i] ~ N时
            dp[i][j] = dp[i + 1][j] > (dp[i + 1][j - p[i]] + v[i]) ? dp[i + 1][j] : (dp[i + 1][j - p[i]] + v[i]);
    }
    dp[1][N] = dp[2][N];
    if (N >= p[1])
        dp[1][N] = dp[1][N] > (dp[2][N - p[1]] + v[1]) ? dp[1][N] : (dp[2][N - p[1]] + v[1]);

}

void Traceback(int dp[][M], int *p, int N, int n, int *x)
{  //p是价格，N是预算，n是商品个数, x是商品是否购买的0/1序列
   //dp[i][j]是在 预算为j，能买的物品为i~n时，所能达到的最大渴望程度和
    int i;
    for (i = 1; i < n; i++)
        if (dp[i][N] == dp[i + 1][N])//说明物品i没有购买（放入背包）
            x[i] = 0;
        else
        {
            x[i] = 1;
            N = N - p[i];
        }
    x[n] = (dp[n][N]) ? 1 : 0;//单独判断最后一个物品n是否购买
}

int main()
{
    int N, K, j;
    int p[M],v[M];//p为价格，v为渴望程度

    N = 2000;//预算
    K = 6;//商品个数
    p[1] = 200;v[1] = 2;
    p[2] = 300;v[2] = 2;
    p[3] = 600;v[3] = 1;
    p[4] = 400;v[4] = 3;
    p[5] = 1000;v[5] = 4;
    p[6] = 800;v[6] = 5;
    Knapsack(v, p, N, K, dp);
    Traceback(dp, p, N, K, x);
    cout << endl;
    int nice = 0;
    for (j = 1; j <= K; j++) {
        nice += p[j] * v[j] * x[j];
    }
    cout << "价格与效益度的乘积的总和为：";
    cout << nice << endl;
    cout << "最大效益度为：";
    cout << dp[1][N] << endl;
    cout << "购物单为：";
    for (j = 1; j <= K; j++)
    {
        if(x[j]) {
            cout << "J" << j << " ";
        }
    }
    return 0;
}